package leetcode_day._2021._202106._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/16 21:05
 * 石子游戏
 * 算法：动态规划   数字
 * dp[i][j], 表示 i 到 j 中两者相差的最大数量
 * dp[i][j] = piles[i] - dp[i + 1][j]
 * piles[j] - dp[i][j - 1]
 */
public class _16_877 {

    public boolean stoneGame(int[] piles) {
        int len = piles.length;
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) dp[i][i] = piles[i];
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                int a = piles[i] - dp[i + 1][j];
                int b = piles[j] - dp[i][j - 1];
                dp[i][j] = Math.max(a, b);
            }
        }
        return dp[0][len - 1] > 0;
    }

    public boolean stoneGame_perfect(int[] piles) {
        return true;
    }

}
